
#include "name_table.h"

namespace qb {
namespace proto{

name_table::name_table()
{
    nodes_ = NULL ;
    count_ = 0 ;
    size_ = 0 ;
}

name_table::~name_table()
{
    clear() ;

    if(nodes_ != NULL)
    {
        ::free(nodes_) ;
        nodes_ = NULL ;
        size_ = 0 ;
    }
}

bool name_table::extend(size_t count)
{
    /*
        分配空间
    */
    size_t nsize = count ;
    if(nsize == 0)
        nsize = next_size() ;

    size_t len = sizeof(node) * nsize ;
    node * nodes = (node *)malloc(len) ;
    if(nodes == NULL)
        return false ;

    memset(nodes , 0 , len) ;

    /*
        拷贝原来的值
    */
    if(nodes_ != NULL)
    {
        for(size_t hidx = 0 ; hidx < size_ ; ++hidx)
        {
            nodes[hidx] = nodes_[hidx] ;
        }

        ::free(nodes_) ;
    }

    size_ = nsize ;
    nodes_ = nodes ;

    return true ;
}

void name_table::clear()
{
    if(nodes_ == NULL)
        return ;

    memset(nodes_ , 0 , sizeof(node) * size_) ;
    count_ = 0 ;
}

int name_table::find(const char * name , size_t hash , int& result) const
{
    result = -2 ;
    if(name == NULL || nodes_ == NULL)
        return -1 ;

    if(count_ == 0)
    {
        //第一个元素为空，
        result = 1;
        return 0 ;
    }

    int begin = 0 , end = count_ - 1 , middle = 0;
    while(begin <= end)
    {
        middle = (begin + end) / 2 ;

        size_t sentry = nodes_[middle].code ;
        if(sentry < hash)
        {
            result = -1 ;
        }
        else if(sentry > hash)
        {
            result = 1 ;
        }
        else 
        {
            node& n = nodes_[middle] ;
            if(name == n.name)
            {
                result = 0 ;
            }
            else
            {
                result = ::strcmp(n.name , name) ;
            }

            if(result == 0)
            {
                return middle ;     //完全一致
            }
        }

        if(result < 0)
        {
            begin = middle + 1 ;
        }
        else
        {
            end = middle - 1 ;
        }
    }

    if(result < 0)
    {
        result = -1 ;
    }
    else
    {
        result = 1 ;
    }

    return middle ;
}

bool name_table::insert(const char * name , size_t hash , size_t value)
{
    if(name == NULL)
        return false ;

    if(nodes_ == NULL || size_ == count_)
    {
        if(extend() == false)
            return false ;
    }

    int result = 0 ;
    int index = find(name , hash , result) ;
    if(index < 0)
        return false ;

    size_t tsize = 0 ;
    if(result != 0)
    {
        if(result < 0)
        {
            //插在index的后面
            ++index ;
        }
        else
        {
            //插在index的前面
        }

        if(index < (int)count_)
        {
            tsize = sizeof(node) * (count_ - index) ;

            memmove(nodes_ + index + 1 , nodes_ + index , tsize) ;
        }

        ++count_ ;
    }
    else
    {
        //相同的hash，只要覆盖就可以了。
    }

    node & n = nodes_[index] ;
    n.name = name ;
    n.code = hash ;
    n.value = value ;

    return true ;
}

bool name_table::unsort_insert(const char * name , size_t hash , size_t value , size_t max)
{
    size_t nsize = (size_ == 0) ? 31 : size_ ;
    for(int idx = 0 ; idx < 32 ; ++idx)
    {
        if(nsize >= max)
            break ;

        nsize = ((nsize + 1) << 1) - 1 ;
    }

    if(nsize < max)
        return false ;

    if(size_ < nsize)
    {
        if(extend(nsize) == false)
            return false ;
    }

    node & n = nodes_[count_] ;
    n.name = name ;
    n.code = hash ;
    n.value = value ;

    ++count_ ;
    return true ;
}

int name_table_node_qsort_cmp(const void * s1, const void *s2)
{
    return name_table::name_table_node_cmp((const name_table::node *)s1 , (const name_table::node *)s2 ) ;
}

bool name_table::batch_sort()
{
    qsort(nodes_ , count_ , sizeof(node) , name_table_node_qsort_cmp) ;
    return true ;
}

bool name_table::batch_insert(const node * ns , size_t count)
{
    clear() ;

    if(ns == NULL || count == 0)
        return true ;

    if(nodes_ == NULL || size_ < count)
    {
        if(extend(count) == false)
            return false ;
    }

    memcpy(nodes_ , ns , sizeof(node) * count) ;
    count_ = count ;

    return batch_sort() ;
}

bool name_table::remove(const char * name , size_t hash)
{
    if(name == NULL || count_ == 0 || nodes_ == NULL)
        return false ;

    int result = 0 ;
    int index = find(name , hash , result) ;
    if(result != 0)
        return false ;

    node& n = nodes_[index] ;
    n.name = NULL ;
    n.code = 0 ;
    n.value = 0 ;

    if(index + 1 != count_)
    {
        size_t mlen = sizeof(node) * (count_ - index - 1) ;
        memmove(nodes_ + index , nodes_ + index + 1 , mlen) ;
    }

    --count_ ;
    return true ;
}


bool name_table::update(const char * name , size_t hash , size_t new_value , size_t *old_value)
{
    if(name == NULL || count_ == 0 || nodes_ == NULL)
        return false ;

    int result = 0 ;
    int index = find(name , hash , result) ;
    if(result != 0)
        return false ;

    node& n = nodes_[index] ;
    if(old_value != NULL)
        *old_value = n.value ;

    n.value = new_value ;
    return true ;
}

bool name_table::insert(const char * name , size_t value)
{
    if(name == NULL)
        return false ;
    
    size_t hash = name_table::hash_value(name , ::strlen(name)) ;

    return insert(name , hash , value) ;
}

bool name_table::remove(const char * name)
{
    if(name == NULL)
        return false;

    return remove(name , name_table::hash_value(name , ::strlen(name))) ;
}

bool name_table::find(const char * name , size_t& value) const
{
    value = 0 ;
    if(name == NULL)
        return false ;

    int result = 0 ;
    int index = find(name , name_table::hash_value(name , ::strlen(name)) , result) ;
    if(index < 0 || result != 0)
        return false ;

    value = nodes_[index].value ;
    return true ;
}

bool name_table::update(const char * name , size_t value , size_t* old)
{
    if(name == NULL)
        return false ;

    return update(name , name_table::hash_value(name , ::strlen(name)) , value , old) ;
}


size_t apr_hash_value(const char * str , size_t size) ;
size_t boost_hash_value(const char * str , size_t size) ;
size_t murmur_hash_value(const char * str , size_t size) ;


size_t name_table::hash_value(const char * str , size_t size) 
{
    return apr_hash_value(str , size) ;
}

int check_null_equal(const void * s1 , const void * s2)
{
    if(s1 == NULL)
    {
        if(s2 == NULL)        
            return 0 ;
        else
            return -1 ;
    }
    else
    {
        if(s2 == NULL)
            return 1 ;
        else if(s1 == s2)
            return 0 ;
        else
            return -2 ;
    }
}

int name_table::name_table_node_cmp(const name_table::node * s1 , const name_table::node *s2)
{
    int result = check_null_equal(s1 , s2) ;
    if(result != -2)
        return result ;

    if(s1->code > s2->code)
        return 1 ;

    if(s1->code == s2->code)
    {
        result = check_null_equal(s1->name , s2->name) ;
        if(result != -2)
            return result ;

        return strcmp(s1->name , s2->name)  ;
    }

    return -1 ;
}

bool name_table::check_nodes() const
{
    return check_nodes(name_table::name_table_node_cmp) ;
}

bool name_table::check_nodes(int (*cmp)(const node * s1 , const node *s2)) const
{
    if(size_ == 0 || count_ == 0)
        return true ;

    for(size_t idx = 0 ; idx < count_ - 1 ; ++idx)
    {
        node& cur = nodes_[idx] ;
        node& next = nodes_[idx + 1] ;

        if(cmp(&cur , &next) >= 0)
            return false ;
    }

    return true ;
}

size_t name_table::next_size()
{
    //size按2的倍数增加,15 --> 31 --> 63
    size_t old_size = size_ ;
    if(old_size == 0)
    {
        old_size = 31 ;
    }
    else
    {
        old_size = ((old_size + 1) << 1) - 1 ;
    }

    return old_size ;
}

size_t boost_hash_value(const char * str , size_t size) 
{
    size_t seed = 0;

    for(size_t idx = 0 ; idx < size ; ++idx)
    {
        seed ^= (size_t)str[idx] + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }

    return seed;
}

size_t boost_hash_prime(int idx)
{
    static size_t primes[ ] = {
    (5ul) , (11ul) , (17ul) , (29ul), (37ul) , (53ul) , (67ul) , (79ul) ,
    (97ul) , (131ul) , (193ul) , (257ul) , (389ul) , (521ul) , (769ul) ,
    (1031ul) , (1543ul) , (2053ul) , (3079ul) , (6151ul) , (12289ul) , (24593ul) ,
    (49157ul) , (98317ul) , (196613ul) , (393241ul) , (786433ul) ,
    (1572869ul) , (3145739ul) , (6291469ul) , (12582917ul) , (25165843ul) ,
    (50331653ul) , (100663319ul) , (201326611ul) , (402653189ul) , (805306457ul) ,
    (1610612741ul) , (3221225473ul) , (4294967291ul)
    } ;

    if(idx < 0 || idx >= 40)
        return 0 ;

    return primes[idx] ;
}


size_t murmur_hash_value(const char * key , size_t length) 
{
 /*
    'm' and 'r' are mixing constants generated offline.  They're not
    really 'magic', they just happen to work well.
  */

  const unsigned int m= 0x5bd1e995;
  const size_t seed= (0xdeadbeef * length);
  const int r= 24;


  // Initialize the hash to a 'random' value

  size_t h= seed ^ length;

  // Mix 4 bytes at a time into the hash

  const unsigned char * data= (const unsigned char *)key;

  while(length >= 4)
  {
    unsigned int k = *(unsigned int *)data;

    k *= m;
    k ^= k >> r;
    k *= m;

    h *= m;
    h ^= k;

    data += 4;
    length -= 4;
  }

  // Handle the last few bytes of the input array

  switch(length)
  {
  case 3: h ^= ((size_t)data[2]) << 16;
  case 2: h ^= ((size_t)data[1]) << 8;
  case 1: h ^= data[0];
          h *= m;
  default: break;
  };

  h ^= h >> 13;
  h *= m;
  h ^= h >> 15;

  return h;
}


size_t apr_hash_value(const char * str , size_t size) 
{
    size_t hash = 0 ;
    const unsigned char * key = (const unsigned char *)str ;
    for(size_t idx = 0 ; idx < size ; ++idx , ++key)
    {
        hash = (hash << 5) + hash + *key ;
    }

    return hash ;
}
}
}

